n=50;
m=1000;
k=20;
D=[2,1,1,4,4,2,5,3,5,5,2,1,3,6,8,6,3,4,2,8,8,9,1,8,8,8,8,2,10,1,7,4,1,6,3,6,8,5,9,8,8,3,6,1,2,9,7,2,1];
T=[8,1,71,4,7,275,43,343,43,218,96,4,1,67,54,21,177,32,41,49,12,127,17,1,124,150,76,1,25,4,85,233,1,28,56,12,61,31,1,283,170,60,31,4,51,20,233,3,55,58,17,64,90,40,34,146,71,20,2,24,19,104,21,1,1,47,60,91,1,9,16,15,1,19,60,68,46,258,11,72,156,28,1,5,23,102,129,96,11,33,38,1,76,8,168,41,1,62,199,19,7,8,198,38,84,1,69,183,10,6,1,52,7,114,4,28,19,31,236,150,116,29,61,246,31,30,8,16,4,111,1,74,83,6,6,2,1,33,179,70,20,150,3,1,9,71,19,74,35,7,137,6,69,36,212,20,58,43,228,7,116,90,121,112,30,160,71,5,7,67,214,159,1,20,2,7,63,16,96,83,8,64,56,281,4,24,71,31,18,22,32,6,7,27,51,20,1,68,5,33,134,55,284,89,64,1,177,95,72,47,9,191,47,43,359,101,54,3,9,16,76,3,30,374,90,17,11,9,162,8,5,61,20,263,100,1,153,1,7,12,3,152,25,386,10,105,16,7,15,98,101,212,13,64,12,58,11,20,14,1,11,1,10,191,45,33,13,36,1,71,1,1,107,2,65,52,192,173,94,241,11,27,89,5,30,33,108,165,1,1,63,31,138,5,187,3,11,3,29,20,1,84,123,48,12,7,7,90,36,158,45,7,72,6,125,30,33,12,154,81,8,40,10,14,11,168,17,56,97,43,32,2,14,92,59,13,186,42,22,11,2,43,21,113,1,1,69,10,14,49,5,17,6,1,92,166,6,137,4,32,255,48,20,57,371,203,63,10,127,13,18,19,98,18,2,73,4,56,267,9,7,148,29,72,34,262,47,151,16,194,173,109,16,7,15,45,45,284,1,9,300,27,309,27,40,41,268,13,4,1,54,127,1,13,3,182,12,216,23,17,131,39,1,297,1,71,10,12,22,10,64,91,13,124,38,35,70,1,121,214,56,30,3,89,56,10,24,1,65,32,105,16,36,4,1,20,99,138,113,69,5,3,16,1,128,101,3,249,183,211,18,16,15,71,9,72,149,115,36,6,61,95,2,147,23,11,182,73,51,151,57,8,19,1,22,37,25,92,1,1,77,22,7,5,65,19,2,36,78,1,29,10,22,127,1,57,16,13,118,20,64,143,25,3,18,101,66,11,57,121,33,1,109,28,32,26,54,17,83,14,127,124,70,120,17,103,98,30,28,120,14,99,38,89,11,8,91,8,88,9,38,6,19,8,17,11,40,234,1,245,182,37,23,359,44,145,153,39,320,81,217,5,183,126,49,12,1,119,184,52,22,4,1,1,26,245,33,81,7,67,109,22,1,22,1,165,12,4,18,12,12,1,167,118,9,137,13,10,84,23,3,46,17,21,62,34,1,18,14,76,1,14,1,1,18,13,1,1,38,144,65,271,138,90,34,37,4,29,46,178,24,27,37,84,40,25,144,13,15,6,20,48,39,9,425,83,94,237,48,8,1,4,16,252,69,11,29,43,162,1,11,49,10,24,3,31,5,46,161,25,2,108,2,70,49,21,119,1,11,102,4,57,50,56,15,11,56,81,106,28,155,48,8,51,157,119,7,65,67,74,90,9,2,221,4,23,162,11,91,103,14,111,50,97,45,170,34,18,24,53,15,16,99,24,61,83,136,29,116,9,11,193,1,39,21,90,188,56,3,12,106,30,28,48,147,9,148,7,41,118,1,235,1,53,9,51,1,19,81,57,14,24,5,13,1,50,34,15,200,315,1,55,280,30,25,4,1,153,25,183,298,4,35,53,9,119,12,35,1,426,57,1,5,157,31,10,24,28,76,18,1,1,109,44,55,201,81,49,17,40,96,31,34,4,1,10,60,39,1,183,12,107,6,158,29,158,20,75,29,46,1,6,21,83,17,14,1,18,261,109,2,31,1,118,11,1,8,141,1,71,168,31,221,32,119,2,2,7,38,41,15,29,30,32,39,14,225,104,142,65,8,18,226,218,38,37,16,3,10,12,71,9,80,23,104,162,3,1,60,61,18,4,1,1,1,13,143,58,160,2,1,6,24,245,85,1,97,1,48,64,20,5,4,73,22,43,27,50,56,338,35,51,23,24,23,27,104,1,65,54,87,34,14,194,38,15,133,141,87,1,14,27,115,28,246,28,16,39,4,49,11,49,21,1,1,75,20,18,22,100,24,4,1,18,133,43,33,27,9,54,7,1,6,17,46,7,27,88,285,195];
A=[16,1,20,2,5,45,11,41,12,35,15,3,1,10,33,3,19,28,5,12,10,28,3,5,28,19,24,1,9,3,11,28,1,20,14,5,9,4,2,31,29,10,6,7,11,6,38,4,13,21,3,11,11,8,6,16,14,13,9,6,4,36,7,1,1,25,40,21,15,2,6,9,2,8,21,21,16,36,3,15,40,11,1,8,4,12,17,18,11,6,7,1,18,6,32,5,1,10,23,6,9,5,31,5,39,1,15,20,2,3,1,17,2,18,3,5,3,10,35,28,29,4,32,27,6,6,20,8,2,30,1,29,12,2,22,42,1,25,19,30,3,38,2,7,5,8,18,13,5,2,19,5,42,17,24,4,22,11,24,2,20,14,20,19,5,29,20,3,12,17,30,17,1,3,4,5,12,6,13,25,2,14,21,34,2,12,19,6,13,16,10,8,2,22,20,13,7,44,4,7,16,7,30,11,10,1,36,15,43,6,3,27,9,14,39,19,10,2,18,15,12,3,6,45,14,3,2,2,38,10,4,18,3,42,24,1,21,1,2,3,3,21,26,42,3,12,3,14,4,30,27,24,3,20,3,8,3,3,17,1,2,1,8,23,7,6,4,10,1,27,1,1,19,6,31,23,33,21,15,25,3,13,23,6,4,6,13,36,1,14,10,4,17,2,30,2,2,5,5,22,1,11,25,28,6,3,6,17,5,23,26,3,12,8,16,4,6,5,28,12,2,14,4,9,20,38,4,8,27,6,18,2,9,24,13,3,27,18,13,3,17,9,15,19,1,1,24,2,8,6,6,7,2,16,31,24,5,15,17,9,30,24,3,15,38,36,11,2,31,5,16,3,20,3,33,21,9,7,30,4,3,36,4,9,11,31,7,19,15,43,21,13,9,2,11,6,9,31,1,2,36,8,33,9,12,12,33,5,3,1,9,25,1,4,2,30,23,24,15,5,16,14,5,31,4,19,2,16,6,2,12,10,10,14,14,9,28,1,16,30,23,5,2,30,19,23,5,8,11,5,16,4,12,3,1,15,24,37,37,8,4,3,12,1,24,28,2,28,27,23,3,21,9,19,2,16,17,28,11,3,18,15,3,17,5,2,30,22,31,22,20,13,5,1,4,6,6,11,1,1,12,43,3,3,8,9,3,24,14,1,5,9,11,36,1,32,5,5,28,6,15,21,17,8,5,17,27,3,7,26,6,1,27,8,14,8,11,10,11,3,14,18,11,32,4,24,11,21,5,24,4,18,5,11,2,4,11,5,27,3,17,2,12,3,4,2,19,36,1,33,24,6,5,47,10,43,32,7,33,9,23,4,36,16,10,4,1,19,24,17,4,2,1,1,5,27,14,9,12,10,23,13,1,6,2,23,12,5,6,5,7,1,21,15,4,15,6,2,36,9,3,6,9,3,10,6,1,6,7,17,1,6,1,1,6,12,1,1,7,21,8,31,17,10,10,40,2,10,12,35,9,6,38,11,23,4,39,3,3,4,4,7,19,9,47,21,11,27,26,2,1,3,13,31,9,5,5,7,24,3,3,16,2,6,2,18,2,10,22,5,2,20,3,22,8,5,14,2,2,18,6,13,8,12,5,8,12,29,17,9,25,17,2,12,33,17,5,8,11,10,11,6,10,25,5,30,24,5,17,16,15,26,13,39,31,46,26,4,8,7,3,5,25,5,8,13,15,7,13,4,5,24,1,14,3,10,22,9,4,5,18,5,26,14,29,2,21,3,7,15,1,32,1,17,2,23,1,4,10,11,17,5,2,23,1,18,15,6,24,44,1,7,37,4,5,2,1,22,8,25,41,2,14,8,4,15,3,13,3,44,21,1,3,24,6,2,6,4,44,7,7,1,24,19,13,36,18,32,11,8,17,4,7,6,1,7,7,11,1,24,3,16,2,19,19,17,3,14,14,34,1,5,3,18,3,4,1,3,29,15,17,4,1,14,2,1,3,23,1,11,34,7,28,17,13,6,3,6,17,14,11,5,6,10,11,23,30,15,20,8,7,5,27,33,28,6,7,3,2,3,14,2,10,9,19,26,3,1,43,8,3,2,1,1,1,6,18,13,28,2,2,3,7,35,40,1,17,1,10,30,4,6,2,12,8,28,4,16,22,41,11,9,7,5,9,4,27,1,37,8,12,6,5,23,8,8,16,33,16,1,4,14,17,10,27,8,25,13,33,34,7,11,3,1,1,18,13,24,15,12,7,9,2,5,15,13,6,9,2,29,4,41,19,5,24,8,10,33,37,41];
B=[23,5,22,16,36,49,12,46,15,38,20,37,10,27,39,35,44,41,20,22,22,42,7,45,49,21,30,7,28,6,15,29,4,27,38,16,22,32,18,41,31,11,23,47,22,9,45,23,29,48,9,24,45,10,41,29,24,39,33,36,7,39,17,46,13,28,42,44,35,32,9,22,13,45,40,28,42,45,5,45,42,15,29,13,20,15,22,27,42,25,15,3,22,7,40,14,2,22,48,7,45,11,38,8,49,7,28,39,14,4,2,27,5,33,16,31,13,32,42,43,45,23,43,33,13,49,42,10,13,32,16,42,18,17,39,45,49,32,24,34,5,48,10,12,24,17,47,20,6,3,33,8,48,18,25,31,38,22,43,6,43,25,38,31,23,32,26,5,18,33,45,24,2,4,49,16,25,9,17,27,33,31,31,45,3,16,29,13,47,35,16,24,8,29,44,22,20,48,18,35,29,17,39,42,17,31,50,26,44,17,22,35,32,31,50,36,12,3,19,24,47,13,48,46,35,27,9,5,43,22,5,37,7,50,30,2,50,45,29,8,24,23,33,48,20,16,10,24,19,33,28,26,29,27,5,18,9,5,43,2,5,33,13,24,33,31,33,27,15,32,6,20,39,41,35,36,43,29,42,28,9,23,46,11,7,35,34,38,3,26,25,6,49,41,40,15,4,8,8,34,4,13,29,35,8,11,35,39,14,27,31,6,28,39,32,8,16,10,35,30,12,16,41,50,33,43,12,9,45,9,42,10,25,32,27,31,30,21,38,35,41,14,49,29,4,3,43,40,26,48,17,24,36,23,40,34,37,32,23,15,37,38,39,48,48,45,36,3,32,24,32,6,47,15,49,49,39,27,49,6,4,40,10,15,37,39,39,27,38,45,33,25,17,13,21,20,28,35,5,3,49,27,41,12,13,44,45,19,4,28,11,28,10,11,9,46,38,44,22,18,38,28,9,46,6,45,3,28,16,4,19,14,26,39,21,15,34,19,48,35,27,9,16,50,46,27,24,11,32,40,41,19,15,10,16,38,32,40,49,9,11,10,44,3,31,35,5,50,29,32,9,25,12,24,11,23,45,34,37,4,45,21,25,22,30,3,41,32,37,30,42,17,27,4,13,23,10,45,49,34,14,49,5,7,11,48,32,35,17,3,23,14,34,37,8,34,8,43,38,48,29,48,46,16,15,18,49,4,31,36,17,4,29,26,19,16,20,16,25,23,27,47,27,35,28,36,14,31,13,30,5,45,23,50,15,17,40,8,28,6,40,18,29,5,8,11,39,49,4,50,28,9,27,50,29,45,37,12,40,41,46,22,48,20,21,20,10,32,44,21,25,40,3,6,13,29,24,15,14,46,29,49,18,29,4,26,13,8,50,14,12,25,47,47,13,18,42,13,49,14,8,7,43,18,37,23,3,41,12,23,17,26,5,4,8,35,2,45,14,26,39,44,22,24,38,47,23,31,23,42,35,40,46,19,26,27,50,50,12,5,6,8,37,22,48,49,44,28,36,5,19,18,16,37,18,7,24,18,47,8,14,38,31,23,50,25,10,34,28,17,35,35,13,45,13,20,23,4,12,21,40,14,21,15,15,30,19,32,39,22,26,34,30,13,39,45,22,13,37,47,21,30,46,43,17,36,46,10,23,44,16,40,19,50,40,49,35,5,30,38,24,25,29,17,10,34,19,38,27,18,11,38,5,19,8,46,39,50,15,7,25,6,46,29,46,12,36,4,22,29,8,39,18,21,5,35,2,21,42,16,37,15,41,28,8,35,45,47,38,46,2,16,39,47,43,24,3,31,18,27,45,30,23,22,10,25,18,16,4,46,34,6,9,25,8,27,21,49,47,23,16,2,43,44,44,48,44,37,49,47,39,13,24,48,32,25,21,19,2,25,7,29,28,31,26,24,6,15,34,38,35,15,29,22,48,7,2,25,39,29,22,32,50,28,15,9,7,37,3,20,36,10,29,20,17,8,37,23,35,32,18,9,20,14,26,36,36,30,28,34,11,10,28,36,44,34,8,5,4,16,45,9,49,24,20,36,15,3,44,48,22,32,3,2,2,22,31,30,45,18,3,4,9,46,48,5,27,3,43,39,14,35,18,34,11,41,45,33,33,48,48,27,19,18,37,8,50,6,39,16,18,7,29,37,9,43,24,44,21,14,5,27,38,12,38,39,30,50,46,43,20,33,45,26,17,35,23,44,39,46,18,13,15,11,24,20,28,11,8,38,18,44,24,7,41,28,15,34,46,46];